package DuplicateDnaSequences;

import java.util.*;

/**
 * @author A2322
 * DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.
 * 例如，"ACGAATTCCG" 是一个 DNA序列
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。给定一个表示 DNA序列 的字符串 s ，
 * 返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。
 * 你可以按 任意顺序 返回答案。
 */
public class Solution {

    /*
     * 这段代码的基本思路是遍历输入字符串，截取长度为 10 的子序列，
     * 并使用哈希表记录每个子序列的出现次数。最后，再次遍历哈希表，
     * 将出现次数大于 1 的子序列添加到结果列表中。
     *
     * */
    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> sequenceCount = new HashMap<>();

        for (int i = 0; i <= s.length() - 10; i++) {
            String sequence = s.substring(i, i + 10);
            sequenceCount.put(sequence, sequenceCount.getOrDefault(sequence, 0) + 1);
        }

        for (Map.Entry<String, Integer> entry : sequenceCount.entrySet()) {
            if (entry.getValue() > 1) {
                result.add(entry.getKey());
            }
        }

        return result;
    }

    /*
     *
     * 这段代码使用了一个长度为 20 位的整数 sequence
     * 来表示长度为 10 的子序列。通过位运算将字符 'A', 'C', 'G', 'T'
     * 转化为 2 位的二进制数字，然后将它们依次添加到 sequence 中，每次左移 2 位。
     * 这个方式可以节省空间，并且能够比较高效地处理 DNA 子序列的哈希值。
     * 然后，代码使用两个哈希集 seen 和 added 来跟踪已经出现的子序列
     * 和已经添加到结果列表中的子序列。当发现一个子序列已经出现过（在 seen 集合中），
     * 但尚未被添加到结果列表中（不在 added 集合中）时，就将该子序列添加到结果列表中，
     * 并将其哈希值添加到 added 集合中，以避免重复添加。
     *
     * */
    public static List<String> findRepeatedDnaSequences1(String s) {
        List<String> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        Set<Integer> added = new HashSet();

        int[] charToInt = new int[26];
        charToInt['A' - 'A'] = 0;
        charToInt['C' - 'A'] = 1;
        charToInt['G' - 'A'] = 2;
        charToInt['T' - 'A'] = 3;

        int n = s.length();
        int sequence = 0;

        for (int i = 0; i < n; i++) {
            sequence = (sequence << 2 | charToInt[s.charAt(i) - 'A']) & 0xFFFFF; // 20-bit sequence
            if (i >= 9) {
                if (seen.contains(sequence) && !added.contains(sequence)) {
                    result.add(s.substring(i - 9, i + 1));
                    added.add(sequence);
                }
                seen.add(sequence);
            }
        }

        return result;
    }
}
